/**
 * @file 087.复原IP.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-17
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    vector<string> restoreIpAddresses(string s)
    {
        path.clear();
        res.clear();
        backtracking(s, 0, 0);
        return res;
    }

private:
    vector<string> res;
    string path;
    bool isValid(string &s)
    {
        if (s.empty() || s.size() > 3) {
            return false;
        }
        // 前导0不合法，单0合法
        if (s.size() != 1 && s[0] == '0' || stoi(s) > 255) {
            return false;
        }
        return true;
    }
    void backtracking(string &s, int startIdx, int pointNum)
    {
        if (pointNum == 3) {
            // check the 4th 部分
            string sub4th = s.substr(startIdx);
            if (isValid(sub4th)) {
                path.append(sub4th);
                res.emplace_back(path);
            }
            return;
        }
        for (int i = startIdx; i < s.size(); ++i) {
            string sub = s.substr(startIdx, i - startIdx + 1);
            if (!isValid(sub)) {
                continue;
            }
            auto lastEnd = path.end();
            path.append(sub);
            path.push_back('.');
            ++pointNum;
            backtracking(s, i + 1, pointNum);
            --pointNum;
            path.erase(lastEnd, path.end());
        }
    }
};

int main()
{
    Solution solve = Solution();
    string s1 = "25525511135";
    string s2 = "010010";
    string s3 = "10203040";
    print(solve.restoreIpAddresses(s1));
    print(solve.restoreIpAddresses(s2));
    print(solve.restoreIpAddresses(s3));

    return 0;
}